package com.LeeCode;

import java.util.HashMap;
import java.util.Map;

/**
 * 根据前序和后序遍历构造二叉树
 */

public class Code889 {
    public static void main(String[] args) {
        int[] preorder = {1, 2, 4, 5, 3, 6, 7}, postorder = {4, 5, 2, 6, 7, 3, 1};
        new Code889().constructFromPrePost(preorder, postorder);
    }

    private Map<Integer, Integer> map = new HashMap<>();

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int n = postorder.length;
        for (int i = 0; i < n; i++) {
            map.put(postorder[i], i);
        }
        return build(preorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode build(int[] preorder, int preLeft, int preRight, int postLeft, int postRight) {
        if (preLeft > preRight) return null;

        TreeNode root = new TreeNode(preorder[preLeft]);

        // 只有一个节点时，无需继续递归
        if (preLeft == preRight) {
            return root;
        }

        int leftRootVal = preorder[preLeft + 1];
        int rootIndexInPost = map.get(leftRootVal);
        int numLeft = rootIndexInPost - postLeft + 1;

        root.left = build(preorder, preLeft + 1, preLeft + numLeft, postLeft, rootIndexInPost);
        root.right = build(preorder, preLeft + numLeft + 1, preRight, rootIndexInPost + 1, postRight - 1);

        return root;
    }
}
